The X-Philes (2nd Revision)/The X-Philes Number 1 (1995).iso/xphiles/hp48_1/list.set

Text File | 1995-03-23 | 8KB | 241 lines

Article 1780 of comp.sys.handhelds:
Path: en.ecn.purdue.edu!pur-ee!mentor.cc.purdue.edu!purdue!tut.cis.ohio-state.edu!cica!sol.ctr.columbia.edu!samsung!usc!apple!dan
From: [e-mail] (Dan Allen)
Newsgroups: comp.sys.handhelds
Subject: RPL Code for Lists/Sets, Rev 2
Keywords: RPL,HP-48SX,lists,sets,set operations
Message-ID: <[e-mail]>
Date: 10 Apr 90 17:09:32 GMT
References: <[e-mail]>
Distribution: comp.sys.handhelds
Organization: Apple Computer Inc, Cupertino, CA
Lines: 225


                    LIST and SET Operations for the HP-48SX
                         By Dan Allen, 10 April 1990
                                Revision 2

LIST PROCESSING
  The HP-48SX supports lists of objects as a built-in data type.  Several
functions are provided for working on lists:

    Function     Operation
    --------     ---------
    +            Concatenates two lists into one list
    SIZE         Returns the number of elements in a list
    POS          Checks if an element is in a list
    SUB          Returns a subset of a list as a list
    GET          Returns the nth element of a list
    PUT          Replaces the nth element of a list

Other than direct editing of a list, there is no way to add elements to a list
other than by appending elements to the front or back of a list through the +
operator, and there is no way to delete elements of a list.
  Here are a few list operations that extend the functionality of the HP-48SX.
Ideally these should be in a future machine; in the meantime they should be
written in assembly language for better efficiency.
  The first two functions are CAR and CDR, named after the LISP functions of
the same bizarre but historically interesting names.  Common LISP also has the
functions FIRST and REST which are exactly the same as CAR and CDR, which
return the first and remaining parts of a list.  The second pair of functions
are INS and DEL, which allow inserting and deleting specific elements of a
list.
  These routines handle invalid arguments quietly, i.e., deleting the 5th
element of a 4 element list does nothing; it returns the 4 element list
unchanged, without any error mentioned.  Similar handling of invalid
conditions is done by the other routines as well.

LISTS AS SETS
  A list supports an ordering of its elements and can have duplicate members.
Sets are not ordered and can only have one occurance of a given object.  With
these restrictions, a list can be used as a set with various functions
designed to support set operations.  Such functions are provided here, with
many of the operations also being valid on lists as well.
  ADJOIN allows items to be added to a set.  ADJOIN makes sure that no
duplicate entries are allowed in the list, thus enforcing one of the rules of
sets.
  MEMBER tests set membership, that is, it checks to see if an object is
included in a set (or list).  It only searches the top level.  It returns a
CDR-like list beginning with the item found, or the empty list { } if the
object is not found.
  UNION and INTERSECT implement set union and intersection, while DIFF and
SDIFF are set difference and symmetric difference.  If the lists given are not
sets (that is, they contain duplicates), duplicates may appear in the results.
These four operations are the main arithmetic operations for sets, with the
following similarities to arithmetic and boolean operations:

   ARITHMETIC            BOOLEAN            SET OPERATION
   ----------            -------            -------------
   addition (+)          OR (inclusive)     union
   subtraction (-)       AND NOT            difference
   multiplication (*)    AND                intersection
   division (/)          XOR                symmetric difference

EXAMPLES

{ 1 2 3 } CAR  -->  1                 { } CAR  -->  { }
{ 1 2 3 } CDR  -->  { 2 3 }           { } CDR  -->  { }

{ 1 2 3 } 1 0 INS  -->  { 0 1 2 3 }   { 1 2 } 9999 48 INS  -->  { 1 2 48 }
{ 1 2 3 } 2 DEL  -->  { 1 3 }         { 1 2 } 9999 DEL  -->  { 1 2 }

{ 1 2 3 } 2 MEMBER  -->  { 2 3 }      { 1 2 3 } 4 MEMBER  -->  { }
{ 1 2 } 3 ADJOIN  -->  { 1 2 3 }      { 1 2 3 } 3 ADJOIN  -->  { 1 2 3 }

{ 1 2 } { 3 4 } UNION --> {1 2 3 4}   { 1 2 } { 1 2 } UNION  -->  { 1 2 }
{ 1 2 } { 3 4 } INTERSECT --> { }     { 1 2 } { 2 3 } INTERSECT  -->  { 2 }
{ 1 2 } { 3 4 } DIFF --> { 1 2 }      { 1 2 } { 2 3 } DIFF  -->  { 1 }
{ 1 2 } { 3 4 } SDIFF --> {1 2 3 4}   { 1 2 } { 2 3 } SDIFF  -->  { 1 3 }

  Comments are bracketed by @ signs.  With minor changes, most of these
programs should run on the HP-28.  Here then are some useful list and set
operations for the HP-48SX:

CAR   @ Extracts the first object of a list as an atomic entity @
<<    @ USAGE:  list CAR  -->   obj   @
  IF DUP SIZE THEN 1 GET END  @ CAR of empty list is an empty list @
>>

CDR   @ Returns the tail (all but 1st object) of a list as a list @
<<    @ USAGE:  list CDR  -->  list   @
  OBJ->
  IF DUP
  THEN 1 - ->LIST SWAP DROP
  ELSE DROP { }   @ CDR of an empty list is the empty list @
  END
>>

INS   @ Inserts an object as the nth element of list @
<<    @ USAGE:  list integer obj INS  -->  list   @
  -> list n x
  <<
    list 1 n 1 - SUB x + list n list SIZE SUB +
  >>
>>

DEL   @ Deletes the nth element of list @
<<    @ USAGE:  list integer DEL  -->  list   @
  -> list n
  <<
    list 1 n 1 - SUB list n 1 + list SIZE SUB +
  >>
>>

MEMBER  @ Checks if obj is a member of list at the top level @
<<      @ USAGE:  list obj MEMBER  -->  list   @
  -> list obj
  <<
    list obj
    IF POS DUP 0 >
    THEN list SWAP list SIZE SUB
    ELSE DROP { }
    END
  >>
>>

ADJOIN  @ Adds an object to a list, preventing duplicates @
<<      @ USAGE:  list obj ADJOIN  -->  list   @
  -> list obj
  <<
    IF list obj MEMBER SIZE
    THEN list
    ELSE list obj +
    END
  >>
>>

UNION  @ Returns the set union of two lists (c = a OR b) @
<<     @ USAGE:  list list UNION  -->  list   @
  OVER -> a b c  @ efficiency tip: put smallest list on top of stack @
  <<
    IF a SIZE 0 == b SIZE 0 == OR
    THEN a b +  @ if either list is empty then concatenate lists @
    ELSE        @ step through the second list's elements @
      b 1 1 b SIZE
      START
        GETI DUP c SWAP
        IF POS
        THEN DROP
        ELSE 'c' SWAP STO+  @ adding appropriate new elements @
        END
      NEXT
      DROP2 c
    END
  >>
>>

INTERSECT  @ Returns the set intersection of two lists (c = a AND b) @
<<         @ USAGE:  list list INTERSECT  -->  list   @
  { } -> a b c  @ efficiency tip: put smallest list on top of stack @
  <<
    IF a SIZE 0 == b SIZE 0 == OR
    THEN c
    ELSE
      b 1 1 b SIZE
      START
        GETI DUP a SWAP
        IF POS
        THEN 'c' SWAP STO+
        ELSE DROP
        END
      NEXT
      DROP2 c
    END
  >>
>>

DIFF  @ Returns the set difference of two lists (c = a AND NOT b) @
<<    @ USAGE:  list list DIFF  -->  list   @
  { } -> a b c
  <<
    IF a SIZE 0 == THEN c
    ELSE IF b SIZE 0 == THEN a
      ELSE
        a 1 1 a SIZE
        START
          GETI DUP b SWAP
          IF POS
          THEN DROP
          ELSE 'c' SWAP STO+
          END
        NEXT
        DROP2 c
      END
    END
  >>
>>

SDIFF  @ Returns the set symmetric difference between two lists (c = a XOR b)
@
<<     @ USAGE:  list list SDIFF  -->  list   @
  { } -> a b c   @ Efficiency note: this is O(n^2) and could be improved @
  <<
    IF a SIZE 0 == THEN b         @ if a is empty, then return b @
    ELSE IF b SIZE 0 == THEN a    @ if b is empty, then return a @
      ELSE                        @ else loop through both lists @
        a 1 1 a SIZE
        START
          GETI DUP b SWAP
          IF POS
          THEN DROP
          ELSE 'c' SWAP STO+
          END
        NEXT
        DROP2
        b 1 1 b SIZE
        START
          GETI DUP a SWAP
          IF POS
          THEN DROP
          ELSE 'c' SWAP STO+
          END
        NEXT
        DROP2 c
      END
    END
  >>
>>